package org.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //1.统计频率
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        //2.创建去重数组
        List<Integer> unique = new ArrayList<>(freq.keySet());

        //3.让前k个位置为频率最高
        quickSelect(freq, unique, 0, unique.size() - 1, k);

        //4.返回前k个元素
        int[] res = new int[k];
        for (int i = 0;i < k; i++){
            res[i] = unique.get(i);
        }

        return res;
    }

    private void quickSelect(Map<Integer, Integer> freq, List<Integer> unique, int l, int r, int k) {
        if(l >= r) return;

        //随机选择基准值
        int key = unique.get(new Random().nextInt(r - l + 1) + l);
        int keyFreq = freq.get(key);//获取key元素的频率
        //三路划分
        int left = l - 1, right = r + 1, i = l;
        while(i < right){
            if(freq.get(unique.get(i)) > keyFreq) Swap(unique, ++left, i++);
            else if(freq.get(unique.get(i))  == keyFreq) i++;
            else Swap(unique, --right, i);
        }

        //[l, left] [left + 1, right - 1] [right, r]
        int a = left - l + 1, b = right - left - 1;
        if(a >= k) {
            quickSelect(freq, unique, l, left, k);
        }else if(a + b >= k){
            return;
        }else{
            quickSelect(freq, unique, right, r, k - a - b);
        }
    }

    private void Swap(List<Integer> unique, int i, int j) {
        int t = unique.get(i);
        unique.set(i, unique.get(j));
        unique.set(j, t);
    }
}